package com.xjj.hash;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class H0030SubstringWithConcatenationOfAllWords {

    // TODO 待优化 1.hash差分比较 2.滑动
    public List<Integer> findSubstring(String s, String[] words) {
        // 由于单词长度固定,匹配逻辑可以转换成先分割,再比较是否有相同多的指定单词
        Map<String, Integer> wordsMap = new HashMap<>();
        int lengths = words[0].length() * words.length;
        for (String word : words) {
            wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < s.length() - lengths + 1; i++) {
            if (compareWords(wordsMap, getGroup(s.substring(i, i + lengths), words[0].length()))) {
                result.add(i);
            }
        }
        return result;
    }

    private Map<String, Integer> getGroup(String str, int length){
        Map<String, Integer> map = new HashMap<>();
        char[] chars = new char[length];
        for (int i = 0; i < str.length(); i++) {
            chars[i % length] = str.charAt(i);
            if (i % length == length - 1) {
                // System.out.println(chars);
                // 计数,单词出现的次数
                map.put(new String(chars), map.getOrDefault(new String(chars),0) + 1);
            }
        }
        // System.out.println(map);
        return map;
    }

    private boolean compareWords(Map<String, Integer> map1, Map<String, Integer> map2) {
        // System.out.println(map1);
        // System.out.println(map2);
        if (map1.size() != map2.size()) {
            return false;
        }
        for (Map.Entry<String, Integer> entry : map1.entrySet()) {
            // 注意这边都是Integer所以没有自动拆箱,千万不能用!=/== 大坑!
            if (!entry.getValue().equals(map2.getOrDefault(entry.getKey(), 0))) {
                // System.out.println(entry.getValue());
                // System.out.println(map2.getOrDefault(entry.getKey(), 0));
                return false;
            }
        }
        return true;
    }

}
